﻿

#include <iostream>
#include <string>
using namespace std;
//顺序表的特点(适合静态,经常定位访问的线性表)
/*
顺序表需要预留存储空间，因此很难恰当预留空间
由于其逻辑顺序与物理顺序的一致性，因此可以按照元素序号(下标)直接存取，具有随机存取的优点
由于保持顺序及物理顺序的一致性，在插入删除时要移动大量数据，因此插入和删除效率低
扩表需要新建一个顺序表，把原白哦数据复制到信标，释放原空间
*/

//线性表的抽象数据类型定义
template<class T>
class List {
public:
    virtual void clear() = 0; //清空线性表
    virtual bool empty() const = 0; //判空，表空返回true，非空返回false
    virtual int size()const = 0;//求线性表的长度
    virtual void insert(int i, const T& value) = 0;//在位序i处插入值为value的元素
    virtual void remove(int i) = 0;//删除位序i处的元素
    virtual int serach(const T& value)const = 0;//查找值为value的元素第一次出现的位序
    virtual T visit(int i)const = 0;//查找位序为i的元素并返回其值，T的数据类型可变
    virtual T visit_front_back(int i)const = 0;//查找位序为i的元素的前驱动后继
    virtual void traverse()const = 0;//遍历线性表
    virtual void inverse() = 0;//逆置线性表
    virtual ~List() {};//空函数，析构函数
};

//自定义异常处理类
class outOfRange : public exception
{
public:
    const char* what()const throw()
    {
        return "Error! out of range. \n";
    }
};
class badSize : public exception
{
public:
    const char* what()const throw()
    {
        return "Error! bad size. \n";
    }
};

//顺序表的类型定义
template<class elemType>//element为顺序表存储的元素类型
class seqList : public List<elemType>
{
private:
    elemType* data;//动态数组
    int curLength;//当前顺序表中存储的元素个数
    int maxSize;//顺序表的最大长度
    void resize();//表满时扩大表空间
public:
    seqList(int initSize = 10);//构造函数，里面是默认参数
    seqList(const seqList& sl);//拷贝构造函数
    ~seqList() { delete[] data; }//析构函数，内存销毁
    void clear() { curLength = 0; }//清空表，只需要curLength为0
    bool empty()const { return curLength == 0; }//判空
    int size()const { return curLength; }//返回顺序表中当前存储元素的个数
    void traverse()const;//遍历顺序表
    void inverse();//逆置顺序表
    void insert(int i, const elemType& value);//在位序i处插入值为value的元素，表长加1
    void remove(int i);//删除位序为i处的元素，表长减1
    int search(const elemType& value) const;
    //查找值为value的元素第一次出现的位序
    elemType visit(int i);//访问位序为i的元素的值，"位序为0"表示第一个元素
    elemType visit_front_back(int i);//访问位序为i的元素的前驱后继
    bool Union(seqList<elemType>  &B);
};

/*函数的实现*/

//构造函数
//构造一个空的顺序表
template<class elemType>
seqList<elemType>::seqList(int initSize)
{
    if (initSize <= 0)
        throw badSize();
    maxSize = initSize;
    data = new elemType[maxSize];
    curLength = 0;
}

//拷贝构造函数
//构造函数里动态分配了内存资源，这时需要用户自定义拷贝构造函数进行深度拷贝
template<class elemType>
seqList<elemType>::seqList(const seqList &sl)
{
    maxSize = sl.maxSize;
    curLength = sl.curLength;
    data = new elemType[maxSize];
    for(int i = 0;i < curLength;++i)
        data[i] = sl.data[i]
}

//遍历顺序表
//访问每一个元素，且只访问一遍，访问含义包含查询，输出，修改元素
//若为空表没有元素，输出"is empty"，否则从第一个元素依次输入所有元素
//由于线性表中当前的元素为curLength，因此下标范围为[0,curLength-1]
//时间复杂度为O(n)
template<class elemType>
void seqList<elemType>::traverse()const
{
    if (empty())
        cout << "is empty" << endl;//空表没有元素
    else
    {
        cout << "output element: \n";
        for (int i = 0; i < curLength; i++)//依次访问数据表中的所有元素
            cout << data[i] << " ";
        cout << endl;
    }
}

//查找值为value的元素
//顺序查找value在线性表中第一次出现的位置，遍历线性表中每个元素依次与value进行比较
//若value == data[i]，则查找成功，i的取值范围是[0,curLength]
//返回data[i]的位序i，否则返回"-1"
//最好情况查找元素为1，比较一次
//假设查找第n个元素，比较n次，设找到第一个元素的概率为p，找到第i个元素所需比较的次数为c
//查找的平均期望为nΣ(i=1) = p*c
//在各个位置上查找成功的概率相同的情况下，查找成功的平均期望为(1+n)/2
//元素定位算法时间复杂度是O(n)
template<class elemType>
int seqList<elemType>::search(const elemType& value) const
{
    for (int i = 0; i < curLength; i++)
        if (value == data[i])
            return i;
    return -1;//查询失败返回-1
}

//查找值为value的元素的前驱后继
//若i=0，则为第一个元素无前驱，否则其前驱为data[i-1]
//若i = curLength - 1,则为最后一个元素，无后继，否则其后继为data[i+1]
//时间复杂度为O(n)
template<class elemType>
elemType seqList<elemType>::visit_front_back(int i)
{
    if (i < 0)
        cout << "the value you search is wrong" << endl;
    else if (i == 0)
        cout << "there's no front \n" << "the back is " << data[i + 1] << endl;
    else if (i == curLength - 1)
        cout << "the front is " << data[i - 1] << "\nthere is no back" << endl;
    else
        cout << "the front is " << data[i - 1] << "\nthe back is " << data[i + 1] << endl;
}

//在位序为i处插入一个值为value的新元素
//顺序表先判断容量是否足够(不够就扩表),插入处i后整体向后移一位，将value插入i位置
//注意插入位置的有效性及表空间是否已满
//i的有效范围是[0,curLength]，表尾data[curLength-1]后面插入元素成为新的表尾是合法的
//并且注意数据的移动方向(最先移动的是表尾元素)
//算法的时间复杂度为O(n)
template<class elemType>
void seqList<elemType>::insert(int i, const elemType& value)
{
    if (i < 0 || i > curLength)//合法的插入范围为[0,curLength]
        throw outOfRange();
    if (curLength == maxSize)//表满，扩大数组容量
        resize();
    for (int j = curLength; j > i; j++)//下标在[curLength-1,i]范围内的元素往后移动一位
        data[j] = data[j - 1];
    data[i] = value;//将值为value的元素放入位序为i的位置
    ++curLength;//实际长度增加1
}

//删除位序为i的值
//直接将data[i+1]到data[curLength-1]的元素整体向前移动一位
//注意要检查删除位置的合法性并且不能对空表做一个删除操作，最好提取出删除的值
//算法的复杂度为O(n)
template<class elemType>
void seqList<elemType>::remove(int i)
{
    if (i < 0 || i > curLength - 1)//合法删除范围为[0,curLength-1]
        throw outOfRange();
    for (int j = i; j < curLength - 1; j++)//下标在[i+1,curLength-1]范围内的元素向前移动一位
        data[j] = data[j + 1];
    --curLength;//表的长度减一
}

//逆置运算
//调整线性表中的元素顺序，可用两两交换元素的方法求解
//即a(0)和a(n-1),a(1)和a(n-2)共进行n/2次交换
//因为首尾对称交换，所以循环控制变量的终值是线性表长度的一半
//时间复杂度为O(n)
template<class elemType>
void seqList<elemType>::inverse()
{
    elemType temp;
    for (int i = 0; i < curLength / 2; i++)//控制交换的次数
    {
        temp = data[i];
        data[i] = data[curLength - i - 1];
        data[curLength - i - 1] = temp;
    }
}

//扩大表空间
//时间复杂度为O(n)
template<class elemType>
void seqList<elemType>::resize()
{
    elemType *p = data;//p指向原顺序表空间
    maxSize *= 2;//表空间扩大2倍
    data = new elemType[maxSize];//data指向新的表空间
    for (int i = 0; i < curLength; ++i)
        data[i] = p[i];//复制元素
    delete[] p;
}

//合并顺序表
//设立三个指针i,j,k，其中i,j为线性表A和B的工作指针，分别赋值为A和B的表尾元素的下标
//k是结果线性表的工作指针，赋值为两表合并之后得到的新表尾的下标
//对i和j所指的元素进行比较，将大的元素加入新表尾k处
//同时其指针和k一起向前移，i指针所指元素继续与j指针所指元素进行比较，直至一个表为空
//若B表中还有元素剩余，则再将剩余元素插入k处，同时j,k指针一起向前移
//算法复杂度为O(m+n)
template<class elemType>
bool seqList<elemType>::Union(seqList<elemType>& B)
{
    int m, n, k, i, j;
    m = this->curLength;//当前对象为线性表A
    n = B.curLength;//m,n分别为线性表A,B的长度
    k = m + n - 1;//k为结果线性表的工作指针(下标)
    i = m - 1;
    j = n - 1;//i,j分别为线性表A，B的工作指针(下标)
    if (m + n > this->maxSize)//判断表A的空间是否足够大
    {
        resize();//表空间不够，扩表
    }
    while (i >= 0 && j >= 0)//合并顺序表，直到一个表为空
        if (data[i] >= B.data[j])
            data[k--] = data[i--];
        else
            data[k--] = B.data[j--];//默认为当前对象，this指针可省略
    curLength = m + n;
    return true;
}

/*线性链表*/
//节点只有一个地址域的链表为单链表，结点有两个地址域的为双链表，首位相连的为循环链表

//单链表每个结点只包含一个指针，指向后继
//单链表结点由数据域(数据元素本身的信息)+指针域(指示后继元素的存储地址)
//即对于每一个数据元素a(i)，除了放置自身的信息外，还要存放其后继a(i)所在的存储地址
//链表结构关心的是节点间的逻辑结构，而不是每个节点的实际地址
//查找元素的方式是"顺藤摸瓜"式(即一个接着一个查)，失去了随机存储的特点，定位运算需要O(n)的复杂度
//但修改元素只需要大量移动，只需要修改指针的指向即可

//头指针为单链表第一个结点的地址存放在一个指针变量中，这个指针变量为头指针
//头指针具有标识一个链表的作用，常用头指针代表单链表的名字
//例如单链表head既代表单链表的名字为head，又表示单链表的第一个结点的地址存储在指针变量head
//首元结点(第一元素点)为存储线性表第一个元素的结点

//头结点的作用在于运算方便，统一(原因在P30页)(头结点的加入使得空表及飞控表的处理一致)
//头结点，整个单链表第一个结点之前加入的一个结点，它的数据域不存储任何信息(可作为监视哨或存放附加信息)
//头结点的指针域存放首元结点的地址
//带头结点的链表为空时，头结点的指针域为null；不带头结点的单链表为空时，头指针null表示空表

/*图片参考数据结构P30 图2.9*/

//单链表的节点类型定义
template<class elemType>
struct Node
{
public:
    elemType data;//数据域
    Node* next;//指针域
    Node(const elemType value, Node* p = NULL)//数据域和指针域的构造函数
    {
        data = value;
        next = p;
    }
    Node(Node* p = NULL)//一个参数的构造函数
    {
        next = p;
    }
};

//利用CPP的new和delete给对象分配空间和释放空间
//Node<elemType>* p = new Node<elemType>(value, NULL);
//上述语句完成了两个操作
//首先申请了一个Node<elemType>类型的存储单元，并给data赋值value，指针赋值NULL
//其次将这块存储单元的首地址赋值给指针变量p，若无足够内存可用，则new在申请内存失败时抛出
//bad_alloc exception异常

//p的类型为Node<elemType> *型，所以无名结点可以用指针p间接引用
//数据域为(*p).data或p->data，指针域为(*p).data或p->next

//单链表的类型定义
template<class elemType>//elemType为单链表存储的元素类型
class linkList :public List<elemType>
{
private:
    struct Node//结点类型
    {
    private:
        elemType data;//结点的数据域
        Node* next;//结点的指针域
        Node(const elemType value, Node* p = NULL)//两个参数的构造函数
        {
            data = value;
            next = p;
        }
        Node(Node* p = NULL)//一个参数的构造函数
        {
            next = p;
        }
    };
    Node* head;//单链表的头指针
    Node* tail;//单链表的尾部指针
    int curLenght;//单链表的当前长度，牺牲空间换时间
    Node* getPosition(int i) const;//返回指向位序为i的结点的指针
public:
    linkList();//构造函数
    ~linkList();//析构函数
    void clear();//将表单清空，使之成为空表
    bool empty()const//带节点的单链表，判空
    {return head->next == NULL;}
    int size()const//返回单链表当前的长度
    {return curLenght;}
    void insert(int i, const elemType& value);//在位序i处插入值为value的结点,表长加1
    void remove(int i);//删除位序为i处的结点，表长减1
    int search(const elemType& value)const;//查找值为value的结点第一次出现的位序
    int prior(const elemType& value)const;//查找值为value的结点的前驱的位序
    elemType visit(int i)const;//访问位序为i的结点的值,0定位到首元结点
    void traverse()const;//遍历单链表
    void headCreate();//头插法创建单链表
    void tailCreate();//尾插法创建单链表
    /*tail是单链表的尾指针，指向尾结点，尾指针使得频繁修改尾结点的值或者后续时，无需从头遍历链表*/
};

//单链表的初始化
//创建一个带头结点的空链表
template<class elemType>
linkList<elemType>::linkList()
{
    head = tail = new Node();//创建带头结点的空表
    curLength = 0;
}

//析构函数
//当链表对象脱离作用域时，系统自动执行析构函数来释放单链表空间
template<class elemType>
linkList<elemType>::~linkList()
{
    clear();//清空单链表
    delete head;//释放头结点
}

//清空单链表
//主要操作为将工作指针从头结点一直移动到表尾，边移动指针边释放结点
//时间复杂度为O(n)
template<class elemType>
void linkList<elemType>::clear()
{
    Node* p;//p为工作指针，指向首元结点
    Node* temp;
    p = head->next;//引入工作指针防止随意修改头指针
    while (p != NULL)
    {
        temp = p;//指针后移
        p = p->next;
        delete temp;
    }
    head->next = NULL;//头结点的指针域置空
    tail = head;//头尾结点均指向头结点
    curLength = 0;
}

//求表长
template<class elemType>
int linkList<elemType>::size()const
{
    //return curLength;//直接返回curLength
    /*上述代码用于设置变量curLength变量用于存储表长*/

    //从第一个结点开始一个一个数，直至表尾
    //设置一个工作指针p和计数器count，每当p指针向后移动一次，count加1直至表尾
    //算法复杂度为O(n)
    Node* p = head->next;
    int count = 0;
    while (p)
    {
        count++;
        p = p->next;
    }
    return count;
}

//遍历单链表
//从头到尾访问单链表的每个节点，并依次输出各个结点的结点域
//时间复杂度为O(n)
template<class elemType>
void linkList<elemType>::traverse()const
{
    Node* p = head->next;//工作指针p指向首元结点
    cout << "traverse:";
    whlie(p != NULL)
    {
        cout << p->data << " ";
        p = p->next;//向后移动指针
    }
    cout << endl;
}

//查照位序为i的结点的内存地址
//合法查找范围为[-1,curLength-1]，当i等于0时，查找的是首元结点，i等于1时，查找的是头结点
//设一个移动指针p和计数器count，初始时p指向头结点，每当指针p指向下一个结点时，计数器count加1，直到p指向位序为i的结点为止
//算法复杂度为O(n)
template<class elemType>
typename linkList<elemType>::Node* linkList<elemType>::getPosition(int i)const
{
    if (i < -1 || i > curLength - 1)//合法查找范围为[-1,curLength-1]
        return NULL;//当i为非法时返回null
    Node* p = head;//工作指针p指向头结点
    int count = 0;
    while (count <= i)
    {
        p = p->next;
        count++;
    }
    return p;//返回指向位序为i的接待你的指针
}

//查找值为value的结点的位序
//设置计数器count从单链表的第一个结点算起，判断当前结点的值是否等于给定值value，查找成功返回结点的位序
//否则继续，直到p==null为止(单链表结束)，查找失败返回-1
//算法复杂度为O(n)
template<class elemType>
int linkList<elemType>::search(const elemType& value)const
{
    Node* p = head->next;//工作指针p指向首元结点
    int count = 0;//首元结点的位序为0
    while (p != NULL && p->data != value)
    {
        p = p->next;
        count++;
    }
    if (p == NULL)
        return -1;//查找失败返回-1(这里的-1并非头结点)
    else
        return count;//查找成功，count为结点的位序
}

//查找值为value的结点的前驱的位序
//从单链表的啊第一个结点开始遍历，设置指针p(正在访问结点)和pre(访问结点的前驱)
//若p==NULL，查找值为value的结点失败，返回-1
//找到值为value的结点，且该结点是首元结点，则无前驱，返回-1
//找到值为value的结点，且该节点不是首元结点，则返回该前驱的位序
//采用以下形式语句序列
/*
    p = head -> next;
    while(没有到达)
        p = p -> next;
*/
template<class elemType>
int linkList<elemType>::prior(const elemType& value)const
{
    Node* p = head->next;//p是工作指针指向首元结点
    Node* pre = NULL;//pre指向p的前驱
    int count = -1;//注意-1表示首元结点无前驱
    while (p && p->data != value)
    {
        pre = p;//前驱指针后移
        p = p->next;//指向下一个待处理点
        count++;
    }
    if (p == NULL)
        return -1;//查找失败返回-1，这里-1并非头结点
    else
        return count;//查找成功，count为结点的位序
}

//插入结点
//假设在位序i插入值为value的结点q，先找到位序为i-1的结点p，让q的指针域指向p原来的后继
//然后修改p的后继为q
//插入的合法范围为[0,curLength]，0表示插入首元结点，curlength表示插在尾结点后面
//算法主要是移动指针查找结点
//算法复杂度为O(n)
template<class elemType>
void linkList<elemType>::insert(int i, const elemType& value)
{
    Node* p;//插入结点的前一个结点
    Node* q;//插入的结点
    if (i < 0 || i > curLength)
        throw outOfRange();//合法的插入位置为[0,curLength]，插入位置非法，抛出异常
    p = getPosition(i - 1);//p是位序为i的结点的前驱
    q = new Node(value, p->next);//申请新结点q，数据域为value，指针域为p->next
    p->next = q;
    if (p == tail)
        tail = q;//q结点插在p结点的后面，若插入点在链表尾，q成为新的尾结点
    curLength++;
}

//删除结点
//删除位序为i的结点，对于有curLength个结点的单链表，合法的删除范围为[0,curLength-1]
//其中0表示删除首元结点，curLength-1表示删除尾结点
//算法的关键在于查询位序为i-1的结点，修改指针的链接关系，算法复杂度为O(n)
template<class elemType>
void linkList<elemType>::remove(int i)
{
    Node* pre;//pre为被删结点前驱
    Node* p;//p为待删结点
    if (i <0 || i > curLength - 1)//合法删除范围为[0,curLength-1]
        throw outOfRange();
    pre = getPosition(i - 1);
    p = pre->next;//p是真正待删除结点
    if (p == tail)
    {
        tail = pre;//待删除结点为尾结点，修改尾指针
        pre->next = NULL;
        delete p;
    }
    else//修改指针并删除结点p
    {
        pre->next = p->next;
        delete p;
    }
}
int main()
{
    
}

